package com.wl2o2o.lanqiao.xzfourteen;

import java.util.Arrays;



/** 
* @author : WLei224
* @date ：2023年3月16日 下午3:38:13 
* 
*/
/**
 * 请问在区间 [2333333, 23333333] 中
 * 有多少个正整数 可以被分解为 12 个质数相乘?
 * @author WLei224
 *
 */
public class 数数 {
    public static void main(String[] args) {
        // 求出区间内的所有质数
        boolean[] isPrime = new boolean[23333334];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= 23333333; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= 23333333; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2333333; i <= 23333333; i++) {
            int num = i;
            int primeCount = 0;
            for (int j = 2; j <= i; j++) {
                if (isPrime[j] && num % j == 0) {
                    primeCount++;
                    num /= j;
                }
                if (primeCount == 12 && num == 1) {
                    count++;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}